1. Einführung
Die thoeretische Informatik
Was bedeutet es zu rechnen? Zu schließen und zu wissen? Gibt es mathematische Funktionen, die man zwar aufschreiben, aber nicht berechnen kann? Gibt es "leichte" und "schwere" Probleme? Was unterscheidet sie voneinander?
Analytische Philosophie und Linguistik
Gottlob Frege, Beriffschrifft des reinen Denkens Philosoph und Mathe
Mathe aber auch der ganze Prozess des Sprechens und Denkens muss formalisiert werden auf axiomatische ebene gestellte mus, auf elementare regeln einigen müssen
Welche eigenschaften müssn automaten haben und formale sprachen zu verarbeiten?
Mathematik und Logik
Lässt sich Mathematik vollständig und widerspruchsfrei durch Axiome beschreiben? (David Hillbert)
Maschinen als Abbild des menschlichen Geistes
Inwiefern unser Denken über formale frage auf maschine abbildbar? Können diese maschinen wie, besser als wir denken? Inwiefern
gibts andere arten computer zu bauen? inwiefern mächtiger als di euns bekannte Wie sieht ein elementarer Computer aus, der die ganze Mathematik berechnen kann?
Turing -> Gibt fragen die man einem computer stellen, die er aber nicht beantworten kann
Unsere computer känenn alle aufgaben erledigen, 20. Jr war nicht so, gab maschine für bestimmte aufbaben
Als universelle rechnermaschinen gab, stellt sich die Frage gibts probleme die schwerer sind zu lösen? (Kompleität, Np-vollständige probleme = Klasse von vollständigen Problmen)
Große Fragen der theoretischen Informatik:
- Sprache und Formel: Informatik ist Formalisierung nicht nur von Mathematik, sondern auch von Linguistik und Philosophie
- Berechenbarkeit: Es gibt mathematische Funktionen, die man zwar aufschreiben, aber überhaupt nicht berechnen kann
- Komplexität: Es gibt Probleme, die man (wahrscheinlich) nicht effizient berechnen kann. P vs NP.
Warum lernen wir theoretische Informatik?
Direkte Abbildungen auf Computer:
Automaten --> Rechnerarchitektur Sprachen --> Programmiersprachen Grammatiken --> Compiler Komplexität --> Algorithmen Information --> Maschinelles Lernen